package cxydmmszl.chapter04.t070;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 龙与地下城游戏问题
 * <li style="color: green;">Desc</li>
 * 给定一个二维数组 map，含义是一张地图，游戏的规则如下：<br/>
 * 1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。<br/>
 * 2）地图中每个位置的值代表骑士要遭遇的事情。
 * 如果是负数，说明此处有怪兽，要让骑士损失血量。
 * 如果是非负数，代表此处有血瓶，能让骑士回血。<br/>
 * 3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于 1。<br/>
 * 为了保证骑土能见到公主，初始血量至少是多少？<br/>
 * 根据 map,输出初始血量。
 * <li style="color: green;">Input</li>
 * 第一行两个正整数 n，m(1≤n,m≤10^3)，
 * 接下来 n 行，每行 m 个整数，代表 map[i][j](−10^3≤map[i][j]≤10^3)。
 * <li style="color: green;">Output</li>
 * 输出一个整数，表示答案。
 * <li style="color: blue;">Link</li> CD45
 *
 * @author habitplus
 * @since 2021-09-13 19:01
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = nextInt();
            }
        }

        int ans = solve(map);
        System.out.println(ans);
    }

    private static int solve(int[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }
        int n = map.length;
        int m = map[0].length;

        // dp[i][j] 表示能达到该位置的最小血量
        int[][] dp = new int[n][m];

        dp[n - 1][m - 1] = map[n - 1][m - 1] < 0 ? 1 - map[n - 1][m - 1] : 1;
        for (int i = m - 2; i >= 0; i--) {
            // 只能向右走，要达到下一个位置的最小血量
            dp[n - 1][i] = Math.max(dp[n - 1][i + 1] - map[n - 1][i], 1);
        }

        int down, right;
        for (int i = n - 2; i >= 0; i--) {
            dp[i][m - 1] = Math.max(dp[i + 1][m - 1] - map[i][m - 1], 1);
            for (int j = m - 2; j >= 0; j--) {
                // 两个方向，向下 和 向右
                down = Math.max(dp[i+1][j] - map[i][j], 1);
                right = Math.max(dp[i][j+1] - map[i][j], 1);
                dp[i][j] = Math.min(down, right);
            }
        }

        return dp[0][0];
    }

}
